//评估字符权重,创建字符权重字典表
function pinggu(str) {
	var dic = new Map();
	for (let i = 0; i < str.length; i++) {
		let c=str[i];
		let a = dic.get(c);
		if (a==null) {			
			dic.set(c,1);
		} else {
			dic.set(c,++a);
		}
	}
	return dic;
}


class Node {
	//id:权值 ch:字符
	constructor(qn,ch) {
		this.qn = qn; //权重 根据权重创建哈夫曼树
		this.ch = ch; //原字符
		this.code = '';//哈夫曼编码
		this.left = null;
		this.right = null;
	}
}

function codeChildren(node, ch) {
	node.code = ch + node.code;
	if (node.left) {
		codeChildren(node.left, node.code+'0');
	}
	if (node.right) {
		codeChildren(node.right, node.code+'1');
	}
}

function sortBy(a, b) {
	return a.qn - b.qn;
}
/**
 * 树是从底部往上建 所以不用知道父节点
 * @param {Object} nodes
 */
function huffmanTree(nodes){
	nodes.sort(sortBy);
	//console.log(nodes);	
	while (nodes.length > 1) {
		//hafuman扩展的父节点 可不可以是实际节点? 答:不可以,会导致编码存在多义性
		var root = new Node(nodes[0].qn + nodes[1].qn,'');
		let node1 = nodes.shift();
		let node2 = nodes.shift();
		root.left = node1;
		//node1以及所有子节点应该拼接一个0作为赫夫曼编码
		//codeChildren(node1, "0");
		root.right = node2;
		//node2以及所有子节点应该拼接一个1作为赫夫曼编码
		//codeChildren(node2, "1");
		nodes.push(root);
		nodes.sort(sortBy);
	}
	codeChildren(nodes[0],'');
}

function map_huffMan(dict) {
	var nodes = new Array();
	dict.forEach(function(value, key, map){
		nodes.push(new Node(value,key));
	});
	huffmanTree(nodes);
	return nodes[0];
}
function arr2_huffMan(qnarr,charr) {
	var nodes = new Array();
	for (let i = 0; i < qnarr.length; i++) {
		nodes.push(new Node(qnarr[i]));
	}	
	huffmanTree(nodes);
	return nodes[0];
}
function arr_huffMan(arr) {
	var nodes = new Array();
	for (let i = 0; i < arr.length; i++) {
		nodes.push(new Node(arr[i][1],arr[i][0]));
	}	
	huffmanTree(nodes);
	return nodes[0];
}
function huffManEncode(str) {
	var dic = pinggu(str)
	var root = map_huffMan(dic);
	//console.log(root);
	var table = new Map();
	findValue(root);
	function findValue(node) { //将赫夫曼树中有字符的节点取出
		if (node.ch != '') {
			table.set(node.ch,node.code);
		}
		if (node.left) {
			findValue(node.left);
		}
		if (node.right) {
			findValue(node.right);
		}
	}
	console.log(table);
	//console.log("二进制赫夫曼编码")
	var result = [];
	for (let i = 0; i < str.length; i++) {
		result +=table.get(str[i]);	
	}
	//console.log("编码长度" + result.length);
	//console.log("编码" + result);
	//下面将二进制编码转换为byte数组（二进制转十进制）
	var codes = [];
	for (let i = 0; i < result.length;) {
		let num = '';
		for (let j = 0; j < 8; j++) {
			if (!result[i]) {
				break;
			}
			num += result[i++];
		}
		//console.log(num);
		//console.log(parseInt(num, 2))
		codes.push(parseInt(num, 2))
	}
	//console.log(codes)
	return new Uint8Array(codes);
}

function huffManDecode(ui8) {
	
	
	let codes = "";
		for (let i = 0; i < s.length(); i++) {
			let curChar = s[i];
			if (curChar == '0') {
				curNode =nodes[curNode].lchild;
			}
			else if (curChar == '1') {
				curNode = nodes[curNode].rchild;
			}
			else {
				exit;
			}
			if (nodes[curNode].lchild == -1 && nodes[curNode].rchild == -1) {
				codes += chars[curNode];
				curNode = 2 * nodeNum - 2;
			}
		}
		return codes;


	return new Uint8Array(codes);
}
//var code = huffManCode(str);

export {
	huffManMap,huffManEncode,pinggu,huffManArr2,huffManArr
};
